/*-------------------------------------------------------------------------
 - Copyright (c) 2024-2025 [XD-AMCC TEAM]
 - [XD-AMCC] is licensed under Mulan PSL v2.
 - You can use this software according to the terms and conditions of the Mulan PSL v2.
 - You may obtain a copy of Mulan PSL v2 at:
 -          http://license.coscl.org.cn/MulanPSL2
 - THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES
 - OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 - TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 - See the Mulan PSL v2 for more details.
 ------------------------------------------------------------------------*/


/**
 * @brief Implement the class hash map.
 *
 * @author  WXQ#XDU
 * @date    2024.11
 */

#include <stdlib.h>

#include "../include/amcc_error.h"
#include "../include/amcc_hashmap.h"

// ------------------------------------------------------------------------
//  HELPER SECTION: for resize the hash map
//

static const unsigned smallPrimes[] = {
    11,     17,     37,     67,     131,
    257,    521,    1031,   2053,   4099,
    8209,   16411,  32771,  65537
};
static unsigned N_smallPrimes = sizeof(smallPrimes) / sizeof(smallPrimes[0]);

// get a prime that greater than or equal to n0
static unsigned prime_correct(unsigned n0){
    for (unsigned i=0; i<N_smallPrimes; ++i) {
        if (smallPrimes[i] >= n0)
            return smallPrimes[i];
    }
    return smallPrimes[N_smallPrimes -1];
}

// get next bigger prime
static unsigned prime_bigger(unsigned prime) {
    for (unsigned i=0; i<N_smallPrimes; ++i) {
        if (smallPrimes[i] > prime)
            return smallPrimes[i];
    }
    return smallPrimes[N_smallPrimes -1];
}

// get previous smaller prime
static unsigned prime_smaller(unsigned prime) {
    for (unsigned i=N_smallPrimes-1; i > 0; --i) {
        if (smallPrimes[i] < prime)
            return smallPrimes[i];
    }
    return smallPrimes[0];
}
//  END OF HELPER SECTION
// ------------------------------------------------------------------------


//  Type of hash map entry(element)
typedef  struct hash_map_entry {
    t_hashcode      hashCode;
    t_map_key       key;
    t_map_value     value;
} t_hashmap_entry, * t_hashmap_entry_ptr;



t_hashmap_ptr  hashmap_new(unsigned capacity_init,
                           t_mapfunc_keyhash fpKeyHash,
                           t_mapfunc_keycomp fpKeyCompare,
                           t_mapfunc_free    fpFree )
{
    if(NULL == fpKeyHash || NULL == fpKeyCompare)// || NULL == fpFree)
        return NULL;

    t_hashmap_ptr pThis = (t_hashmap_ptr)calloc(1, sizeof(*pThis));
    if (NULL == pThis )
        return NULL;

    pThis->capacity = prime_correct(capacity_init);  // a smaller prime
    pThis->buckets  = (t_list_ptr)calloc(pThis->capacity, sizeof(t_list));
    if (NULL == pThis->buckets) {
        free (pThis);
        return NULL;
    }
    for (unsigned i=0; i < pThis->capacity; ++i){
        list_init (&(pThis->buckets[i]) , NULL);
    }

    pThis->count_of_keys = 0;
    pThis->fpKeyHash     = fpKeyHash;
    pThis->fpKeyCompare  = fpKeyCompare;
    pThis->fpFree        = fpFree;
    return pThis;
}

static t_hashcode hashmap_hash(t_hashmap_ptr pThis, t_map_key key) {
    t_hashcode h = pThis->fpKeyHash(key);
    return h ^ (h >> 16);
}

static bool hashmap_keyeq (t_hashmap_ptr pThis,
                           t_hashmap_entry_ptr entryPtr,
                           t_map_key key, t_hashcode keyHash)
{
    if ( entryPtr->hashCode != keyHash ) return false;
    if ( key == entryPtr->key ) return true;
    return (0 == pThis->fpKeyCompare(key, entryPtr->key) );
}


typedef struct visit_data {
    t_hashmap_ptr mapPtr;
    void * fp_visit;
    void * user_data;
} t_visit_data;

// Inner callback function for map_clean(): destroy one entry of map
static int callback_freeEntry (t_list_app_value pEntry, void* visit_data) {
    t_visit_data * udata   = (t_visit_data *)visit_data;
    t_hashmap_entry_ptr entryPtr = (t_hashmap_entry_ptr)pEntry;

    if (NULL != entryPtr && NULL != udata && NULL != udata->fp_visit) {
        udata->mapPtr->count_of_keys -= 1;
        t_mapfunc_free freeFunc = (t_mapfunc_free)(udata->fp_visit);
        t_map_key   key   = (t_map_key)(entryPtr->key);
        t_map_value value = (t_map_value)(entryPtr->value);
        freeFunc ( key, value );   // call user function to free key and value
        free ( entryPtr ); // free this entry itself
    }
    return 0;
}


void hashmap_clean (t_hashmap_ptr   pThis) {
    if (NULL == pThis) return ;
    if (NULL != pThis->buckets) {
        t_visit_data  visit_data;
        for(unsigned i=0; i < pThis->capacity; ++i) {
            t_list_ptr listPtr = &(pThis->buckets[i]);
            visit_data.mapPtr    = pThis;
            visit_data.fp_visit  = pThis->fpFree;
            visit_data.user_data = NULL;

            // free each entry in this list, then clear this list
            list_foreach( listPtr, callback_freeEntry, &visit_data);
            list_clean( listPtr );
        }
    }
    pThis->count_of_keys = 0;
}


void hashmap_destroy (t_hashmap_ptr pThis) {
    if (NULL == pThis) return;
    if (NULL != pThis->buckets) {
        hashmap_clean (pThis);
        free (pThis->buckets );
    }

    free (pThis);
}

int  hashmap_size (t_hashmap_ptr pThis) {
    if (NULL == pThis || NULL == pThis->buckets) return 0;
    return pThis->count_of_keys;
}

#define BUCKET_INDEX(mapPtr, hashCode)  (unsigned)((hashCode) % (mapPtr)->capacity)
#define BUCKET_LIST(mapPtr, hashCode)   (&((mapPtr)->buckets[ BUCKET_INDEX(mapPtr, hashCode) ]))


t_mapresult_insert hashmap_remove (t_hashmap_ptr pThis, t_map_key key) {
    t_mapresult_insert result;
    result.success = false;
    result.value = NULL;

    if (NULL == pThis || NULL == key)
        return result;

    t_hashcode hashCode = hashmap_hash(pThis, key);
    t_list_ptr  listPtr = BUCKET_LIST(pThis, hashCode);

    list_remove_if(listPtr, NULL, NULL);

    t_list_iterator  itr;
    LIST_ITERATOR_INIT ( &itr, listPtr );
    t_list_node_ptr node = LIST_ITERATOR_BEGIN ( &itr );
    t_list_node_ptr end  = LIST_ITERATOR_END   ( &itr );

    for (t_hashmap_entry_ptr entryPtr ;
         node != end ;
         node = LIST_ITERATOR_NEXT ( &itr ) )
    {
        entryPtr = (t_hashmap_entry_ptr)list_node_get_value(node);
        if ( NULL == entryPtr )
            continue;
        if ( false == hashmap_keyeq(pThis, entryPtr, key, hashCode) )
            continue;

        result.success = true;
        result.value = entryPtr->value;
        list_remove(listPtr, node);

        t_visit_data visit_data;
        visit_data.mapPtr    = pThis;
        visit_data.fp_visit  = pThis->fpFree;
        visit_data.user_data = &result;
//        --(mapPtr->count_of_keys);
        callback_freeEntry(entryPtr, &visit_data);
        break;
    }

    return result;
}


// find the mapped value of the key with hashCode
static t_hashmap_entry_ptr
findValue_INNER (t_hashmap_ptr pThis, t_hashcode hashCode, t_map_key key)
{
    t_list_ptr       listPtr = BUCKET_LIST(pThis, hashCode);
    t_list_iterator  itr;
    LIST_ITERATOR_INIT ( &itr, listPtr );
    t_list_node_ptr node = LIST_ITERATOR_BEGIN ( &itr );
    t_list_node_ptr end  = LIST_ITERATOR_END   ( &itr );
    for (t_hashmap_entry_ptr entryPtr ;
         node != end ;
         node = LIST_ITERATOR_NEXT ( &itr ) )
    {
        entryPtr = (t_hashmap_entry_ptr)list_node_get_value(node);
        if ( NULL == entryPtr ) continue;
        if ( false == hashmap_keyeq(pThis, entryPtr, key, hashCode) )
            continue;

        return entryPtr;
    }

    return NULL;
}


t_map_value hashmap_find (t_hashmap_ptr pThis, t_map_key key) {
    if (NULL == pThis || NULL == key) return NULL;
    t_hashcode hashCode = hashmap_hash(pThis, key);
    t_hashmap_entry_ptr result = findValue_INNER(pThis, hashCode, key);
    return (NULL == result) ? NULL : result->value;
}


static inline
t_hashmap_entry_ptr newEntry (t_hashcode hashcode, t_map_key key, t_map_value value) {
    t_hashmap_entry_ptr entryPtr = calloc(1, sizeof(*entryPtr));
    if (NULL == entryPtr) {
        ERROR_REPORT_MALLOC();
    } else {
        entryPtr->hashCode = hashcode;
        entryPtr->key = key;
        entryPtr->value = value;
    }
    return entryPtr;
}


t_mapresult_insert  hashmap_put (t_hashmap_ptr pThis,
                                 t_map_key key,
                                 t_map_value value )
{
    t_mapresult_insert result;
    result.success = false;
    result.value = NULL;

    if (NULL == pThis || NULL == key || NULL == value)
        return result;

    // not____TODO: enlarge this map on demand

    t_hashcode hashCode = hashmap_hash(pThis, key);

    // find the same key
    t_hashmap_entry_ptr entryPtr = findValue_INNER(pThis, hashCode, key);
    if ( NULL != entryPtr ) {
        result.success = false;
        result.value = entryPtr->value;
    } else {
        entryPtr = newEntry(hashCode, key, value);
        if (NULL != entryPtr) {
            t_list_ptr listPtr = BUCKET_LIST(pThis, hashCode);
            if (NULL == list_prepend(listPtr, entryPtr)) {
                free (entryPtr);
                ERROR_REPORT_MALLOC();
            } else {
                ++ (pThis->count_of_keys) ;
                result.success = true;
                result.value = NULL;
            }
        }
    }

    return result;
}



// local callback function for map_foreach()
static int callback_visitEntry (t_list_app_value entry, void * visit_data) {
    t_hashmap_entry_ptr entryPtr = (t_hashmap_entry_ptr) entry;
    t_visit_data *      udata    = (t_visit_data *) visit_data;

    if (NULL != entryPtr && NULL != udata && NULL != udata->fp_visit) {
        t_mapfunc_visit visit = (t_mapfunc_visit)(udata->fp_visit);
        return visit ( entryPtr->key, entryPtr->value, udata->user_data );
    }

    return 0;
}


int hashmap_foreach (t_hashmap_ptr   pThis,
                     t_mapfunc_visit fp_visit,
                     void* user_data )
{
    if (NULL == pThis || NULL == pThis->buckets)
        return 0;

    int  visitResult;
    t_visit_data  visit_data;
    visit_data.fp_visit  = fp_visit;
    visit_data.user_data = user_data;
    for (unsigned i = 0; i < pThis->capacity; ++i) {
        visitResult = list_foreach (&(pThis->buckets[i]),
                                    callback_visitEntry,
                                    &visit_data );
        if( visitResult != 0 )
            return visitResult;
    }

    return 0;
}
